Not applicable
Not applicable
Not applicable
The present invention relates generally to computerized methods for analyzing and solving decision problems, for globally optimizing the operation of systems and processes, and for designing graphical user interfaces. More specifically, the invention provides software methods and a graphical user interface for solving decision and system optimization problems involving sequential, probabilistic and multi-objective decisions.
Introduction
Artificial Intelligence (AI) may be defined as the art of creating methods and machines for performing functions requiring various forms and degrees of natural intelligence when attempted by humans. Considerable advances have been made since the late 1970s by computer scientists, operations researchers and system scientists in applying the results of AI research to the construction of computational tools for automating various processes in the art of decision making and risk analysis [14, 17]. Such advances have been especially successful in the field of Decision Analysis, where mathematical and statistical modeling methods have been combined with computational techniques to develop new tools to assist Decision Makers in selecting an optimal choice from a plurality of choices [1-3, 9, 19-30, 56].
While there is no unique method for solving complex decision problems, the flowchart of FIG. 1 illustrates the major steps currently guiding decision analysts. Software developers have implemented these steps in a variety of ways, and important technical terms have received different descriptions throughout the literature. To distinguish the invention disclosed herein from the current art, a precise definition of some critical terms of art is needed.
Technical Definitions
Concepts From Graph Theory
A graph G=(N, E) consists of a set N={n1, n2, . . . } of nodes and a set E ⊂ Nxc3x97N of edges or arcs. For any edge e=(u, v) in E, we say that nodes u an v are adjacent. When (u, v) is an ordered pair, it is a directed edge, where u is adjacent to v and v is adjacent from u, u is called the parent of v and v is called the child of or offspring of u. When every edge in G is an ordered pair, G is called a directed graph, or digraph.
A path in G from v1 to vk is a sequence  less than (v1, v2), (v2, v3), . . . , (vkxe2x88x922, vkxe2x88x921), (vkxe2x88x921, vk) greater than  of adjacent edges, sometimes written  less than v1, v2, . . . , vk greater than , where each node is distinct, except possibly for v1=vk, in which case the path is called closed, and said to constitute a cycle or circuit. Otherwise the path is called open.
A node w in N is said to be isolated if there does not exist an edge (u, v) in E for which either w=u or w=v. A node is called a root of G if there are paths from u to every other node in G. A graph G is connected if, for every pair (u, v) of nodes in N, there exists a path from u to v or from v to u. A graph H=(M, D) is a sub-graph of G=(N, E) if M⊂N and D⊂E. In a subgraph H of G, a node w in M is called a root in G if w is a root of H. Whenever there exists a path from a node u to another node v in a directed graph G, v is a descendant of u and u is an ancestor of v.
A graph G is a tree if there exists exactly one path between any two distinct nodes of G. A directed graph G is a directed tree, tree for short, if G has a root r and there exists exactly one directed path from r to every other node of G. When a graph G is a tree, any sub-graph of G is also a tree, a sub-tree of G. In a tree, every node has at most one parent, and whenever a tree has a unique root, it is called a rooted tree. A node u in a tree G is a leaf node or terminal node if u has no offspring, and similarly for any sub-tree H of G.
Hierarchies
A hierarchical graph with P levels is an object HG=(N, E, H), where
1. (N, E) is a directed and rooted tree
2. H= less than H1, H2, . . . , Hp greater than , an ordered partition of N, i.e.
(i) ∪Hi=N and Hi∩Hj=xcfx86, for i and j from l to P, i≈j, and
(ii) for every edge e=(u,v) in E, if u is in Hi and v is in Hj, then i greater than j.
For any partition element Hi, a node in Hi is a node at level i. For any edge (u, v) in E, u is superior to v and v is subordinate to u if, and only if, u is in Hi, v is in Hi and i greater than j.
An important application of hierarchical graphs arises when decision problems are motivated by a multiplicity of competing objectives. An objective is a statement of action whose purpose is to attain a desired state or condition. Whenever the nodes of a hierarchical graph represent objectives, the graph is called an objectives hierarchy. Statements such as xe2x80x9cminimize lossesxe2x80x9d, xe2x80x9cmaximize profitxe2x80x9d, xe2x80x9cincrease reliabilityxe2x80x9d and xe2x80x9creduce environmental risksxe2x80x9d are examples of objectives associated with typical decision problems. For any edge (u,v) in E, if u and v are objectives, if u belongs to H1 and v belongs to Hj and i greater than j, then u is the super-objective of v and v is a sub-objective of u, and similarly when i less than j.
Semantics of Graphs, Trees and Hierarchies
The terms introduced in the previous sections are used to define graphical and mathematical relationships between nodes, edges and levels. These are topological relationships and, taken collectively, they constitute the topology of the defined graph, tree or hierarchy.
When used as models of some reality, these constructs must be assigned some meaning. This is accomplished by adding another descriptive layer called the semantic layer, where a contextual meaning is attached to the nodes, edges and levels. To illustrate this combination of topology and semantics, consider now a modeling construct that will serve as a basic building block for this disclosure.
Probalistic Decision Trees
A Probabilistic Decision Tree (PDT) is a model of a decision problem that represents all the choices, consequences and paths that a decision maker may experience through time. In very general terms, the major purpose for building and solving a PDT is to find choices that satisfy a decision maker""s definition of xe2x80x9coptimalxe2x80x9d. Another purpose is to evaluate the consequences and collateral risks resulting from the implementation of a given choice, optimal or not. Throughout this disclosure, risk is defined as the numerical value resulting from a finite summation R=xcexa3(pi*ci) of product pairs (pi*ci), where the cis constitute a collection of mutually exclusive and exhaustive events and, for every i, pi is the probability of occurrence of ci. When a decision maker faces a plurality of choices and uses risk as an optimization criterion, his or her optimal choice is the choice whose selection minimizes risk.
While the ci terms are often interpreted as the occurrence of some cost or penalty, no such restrictions apply here, and they may assume any scalar value, positive or negative. Since R has the same form as the expectation operator in the theory of probability and statistics, it is often called the xe2x80x9cExpected Riskxe2x80x9d and, when R is negative, the xe2x80x9cExpected Benefitxe2x80x9d.
The topological structure of a PDT is a directed (and rooted) tree whose nodes are of three types, decision nodes, chance nodes and terminal nodes. Referring to FIG. 3, a decision node 4, drawn as a square, represents a decision to be made. A chance node 5, drawn as a circle, represents a random chance variable, and a terminal node 6, drawn as a vertical ellipse, represents a leaf in the tree. An offspring 8 of a decision node 4 is a choice available at that node, and an offspring 9 of a chance node 5 is a consequence or outcome associated with the chance node. The offspring of every chance node constitute a mutually exclusive and exhaustive set of consequences or outcomes. Edges relating a node to its offspring are occasionally referred to as branches.
While it usually correct to view parent nodes as preceding their offspring on some underlying time scale, standard PDTs are not endowed with any numerical scale on which the timing of events is quantitatively specified, and only a relative timing is suggested.
The contextual meaning of a PDT is contained in its semantic layer. Each node receives a node label and each directed edge (u,v) receives a transition cost or transition benefit representing the cost or benefit incurred during a transition from u to v. When u is a chance node, a transition probability is also assigned to (u,v) to indicate the probability of occurrence of Outcome v. The semantic elements of PDTs are discussed in greater depth in the detailed description of the invention.
Probabilistic decision trees must satisfy some obvious constraints. First, the decision maker may select only one choice at every decision node. Second, since outcomes at any node must constitute a mutually exclusive and exhaustive collection, the outcome probabilities at any chance node must sum to unity.
Probabilistic Decision Graphs
Large PDTs often contain repeated sub-trees, sub-trees whose topologies are identical. Sometimes these sub-trees also possess identical semantics. In either situation, a tempting modeling approach consists of retaining only one of the repeated sub-trees as a prototype, ignoring the other sub-trees, and providing some connection from the parent of each ignored sub-tree (the parent of its root) to the root of the prototype. This restructuring is typically accomplished by replacing the root of each subtree with a new node called a reference node or continuation node 7, which is drawn here as a horizontal ellipse, and by inserting one new edge from each such node to the root of the prototype.
This approach usually simplifies the graphical representation of a decision model and occasionally yields computational benefits as well. It comes at a price, however. If the semantics of the sub-trees do not agree, and especially if the sub-trees have different ancestral dependencies, the differences must be accounted for in the prototype, a potentially complicated task.
Second, the tree structure of the model is now destroyed, since the root of the prototype now has more than one parent, and the resulting model is no more than a Probabilistic Decision Graph (PDG). Since the new reference edges may point to nodes anywhere in the tree, the topology of the PDG may include loops or cycles, increasing the computational complexity of the model. Due to such difficulties, the potential computational advantages associated with repeated sub-trees have not been sufficiently exploited by developers of decision tree analysis software [19, 20, 22-27, 30]. In the current art, the benefits of such model reductions are confined to graphical advantages where the repeated sub-trees are simply hidden from view, but the model itself is still solved as a PDT in the background. Improved methods are needed to better exploit the redundancy inherent in repeated sub-trees by providing reduced models that can be solved more efficiently, and with no loss in accuracy.
Sequential Decision Networks
Many decision problems involve attributes such as costs, rewards and probabilities that are time-dependent, and may also be functions of ancestral node properties. This requires a generalization of standard probabilistic decision trees and graphs since these only provide a chronological ordering of nodes and events. Such a generalization is provided by Sequential Decision Networks (SDN), also called Dynamic Networks or Time-Expanded Networks [2,33,53]. Whereas the topological axioms of SDNs and PDNs are the same, the generalization resides in the semantic layer, where a much richer association of values, variables and functions is allowed. The art of decision analysis software must be extended to include this important generalization.
Background of the First Preferred Embodiment
The flowchart 1 of FIG. 1 illustrates the major steps used to solve decision problems using Sequential Decision Networks. The purpose of the first step is to informally describe the decision maker, his or her decision problem, other stakeholders, the decision urgency and priority, and any problem constraints.
The symbolic representation of decision problems is initiated during the second step, where the decision maker""s objectives are stated and structured, usually in the form of an objectives hierarchy [4,5,9,10,12,13,50,55]. There is little disagreement among practitioners of the art that this is a critical step in the formulation and solution of decision problems, for one dominant reason: multiple-objective problems are solved by optimizing an objective function, a numerical function of multiple performance measures. Each measure is derived from a corresponding objective in the hierarchy, and is designed to indicate the degree to which the corresponding objective is satisfied. A careless construction of the objectives hierarchy will produce a collection of measures that inadequately represent the decision maker""s problem and may lead to catastrophic errors during the computation of an optimal choice.
This rather obvious fact notwithstanding, software developers [19-30] have found it difficult to formally and seamlessly integrate objectives hierarchies with their decision analysis software. Although software packages for structuring objectives and organizational charts are readily available as separate packages, they have not been seamlessly integrated with existing tools for solving sequential decision problems. The absence of such an integrated capability is a significant limitation in the current art.
In all but rare cases, the overall objective function introduced earlier is a many-to-one function of performance measure values, each value weighted in accordance with a priority assignment on the corresponding objectives, and in agreement with the decision maker""s preferences about these values. Although the objectives hierarchy""s level structure may suggest a qualitative ranking of objectives, additional steps are required to elicit a numerical and rational prioritization from the decision maker [1,4,5,9,10,13,31]. These important steps cannot be found in the art of sequential decision analysis software.
To adequately account for a decision maker""s preferences about performance values, the invention disclosed herein is utility-based [3,5,8,9,11,50] in the sense that a utility function is specified on the range of each performance measure. The sole but effective purpose of a utility function is to formalize the utility to the decision maker of achieving given values of performance measures in accordance with a set of rules that have been defined as rational [8-11]. The resulting objective function is thus a function of utility values, weighted by the objective priorities. The fact that performance values are achieved probabilistically when chance nodes are present will be discussed later, when the expected utility criterion is formally introduced. The notion of utility is crucial in obtaining rational solutions to decision problems. Yet, it is also absent from current sequential decision software implementations.
Continuing with the flowchart 1, four major steps are required to specify the interconnection topology of sequential decision networks, starting with decision nodes and concluding with terminal and continuation nodes. Persons familiar with the art will recognize these steps as standard in the development of probabilistic decision trees. At a more detailed level, however, two improvements must be made to the current art.
The first concerns policy preemptions, defined here as the a-priori preemption of one or more decisions represented in the decision model. Such user choices must be accommodated during program execution by proceeding without interruption on the assumption that preempted nodes are reduced to a single choice. As an extreme case, the user may preempt every decision, in which case the decision problem is solved a-priori. The second exception arises in the computation of probabilistic graphs that include reference or continuation nodes. Current technology is limited to hiding repeated sub-trees from view, and does not sufficiently exploit the computational advantages associated with sub-trees that share a topological or semantic structure.
Two final steps are required to complete the formulation of semantics. In the first step, the contributions to performance measures incurred during transitions or edge traversals are specified. The second step is used to specify the probabilities associated with transitions from chance nodes to their offspring. The art of decision making includes various methods for eliciting and encoding probabilities from decision makers [9,31,32,55]. Such methods provide various degrees of rationality in estimating the probability of chance outcomes and significantly reduce the subjective variability associated with simple guesses. Some of these methods should be integrated as standard components in any decision analysis software.
As shown in the flowchart, the construction of a Sequential Decision Model (SDM) is an iterative process where the elicitation of probabilities is often the final step. The topological structure of a SDM resides in its sequential decision network and in its objectives hierarchy, and its semantic layer is defined by its objectives with their priorities, the performance measures, the utility functions, and by the costs and probabilities associated with network edges.
Sequential decision models are typically solved by executing two procedures [2,24,27,30]. The first is a forward roll, during which forward cumulative objective function values are computed, starting at the root and ending at the leaves or terminal nodes of the network. Cumulative path probabilities and risks are also calculated during this forward procedure. The second is a backward roll, during which backward cumulative values are calculated, starting at the terminal nodes and terminating at the root. At each chance node, the second procedure performs an expected risk calculation, an expectation process where the backward value associated with each outcome is multiplied by the outcome""s probability of occurrence and the resulting products are summed. At each decision node, the procedure calculates the maximum value of its choices. The overall process terminates at the root node, yielding the choice with the largest expected value, the optimal choice.
When certain model parameters are critical in the decision-making process, or when some parameters are highly subjective, ambiguous, uncertain or controversial, a sensitivity analysis is often performed to establish the extent to which variations in such parameters influence the final choice. Similar to Monte Carlo simulation experiments, such sensitivity analyses grow geometrically in the quantity of varied parameters and in the quantity of values used for each parameter. This causes a combinatorial growth in the required number of calculations, often leading to unacceptable run times. Nevertheless, every decision analysis software package should provide a capability to conduct thorough sensitivity analyses on all the important parameters of a decision problem.
Graphical User Interface
During the last decade, considerable advances have been made to improve the accessibility of decision-making software to users who, while needing assistance with their decision problems, have only limited training or experience in decision theory or computer science. Even though some applications provide improved man-machine interfaces, users must still perform many operations that should be executed in the background. Some of the leading applications [22,25,27] may still be classified as xe2x80x9cprogramming languagesxe2x80x9d. Such products are mostly intended for trained decision analysts and computer scientists.
A computer""s principal purpose is to assist humans in solving problems. Today, in the same spirit in which personal computers were invented, a major objective in the computer research and development industry is to produce more user-friendly machines and applications. The availability of word processors has revolutionized the modern office, where professional typists are no longer required to generate written communications. Similar improvements to existing decision analysis software are needed to attract a much larger base of decision makers who are intimidated by current software products and cannot afford to employ professional decision analysts. Better Graphical User Interfaces (GUI) are needed and can be produced without compromising the range and quality of decision solutions.
Current Software Implementations
The current art contains two prominent approaches for solving probabilistic decision models, the Monte Carlo Simulation (MCS) approach, and the Direct Probability Computation (DPC) approach. The principal distinction between the two methods resides in the processing of chance nodes, and may be best understood by viewing a chance node as a random variable [1] whose values represent the node""s outcomes.
The MCS procedure, as applied in [20-23], consists of a series of simulation runs, one run for every combination of statistical samples selected from the distributions associated with the chance variables and with other random parameters in the model. Several sampling methods such as Importance Sampling, Latin Squares and Hypercubes [43] have been developed to improve the computational inefficiency of brute-force MCSs. Such methods are of limited use in complex decision problems, where the time required to converge to statistically confident estimates increases geometrically in the total quantity of chance node and random factor value combinations. As an example, for k chance nodes and random factors, each having m possible values, the quantity of runs required to achieve an acceptable confidence level is typically proportional to mk, a geometric increase in m.
In contrast to MCS approaches, the DPC method, as applied in [19,24-27,30], processes chance outcome probabilities directly during the computation of optimal choices. Instead of the combinatorial requirements of MCS procedures, the DPC approach requires only a single run since the expectation operation at each chance node integrates the outcome probabilities with outcome weights into a single number, and no sampling is needed. Although this aggregation hides some of the finer statistical structure of decision models, a sensitivity analysis, accompanied with the computation of risk profiles, significantly reduces the possible harmful effects of ignoring the finer structure.
The major reason for contrasting these two computational paradigms is to argue that improvements in the art should concentrate on the direct approach. Furthermore, these improvements must be implemented in stand-alone software that can be executed on a variety of computational platforms. Products such as @Risk(trademark) [20], Precision Tree(trademark) [19], Crystal Ball(trademark) [23] are Microsoft Excel(trademark) add-ons that are confined to the Excel(trademark) interface and worksheet format. This severely limits the practicality and possibility of extending such PDT implementations to probabilistic decision networks as defined earlier.
Brief Summary of the First Embodiment
In its first preferred embodiment, the current invention""s general object is to provide a method and means for assisting individuals, businesses, organizations and consultants in solving complex decision problems and performing risk analyses and risk assessments. In this disclosure, we define xe2x80x9cRiskxe2x80x9d as a summation of consequence-probability pairs (c, p), where c is an outcome of a chance event and p is the probability of occurrence of c. When a decision maker faces a plurality of choices and uses risk as an optimization criterion, his or her optimal choice is the choice whose selection minimizes risk. This first embodiment improves the art of decision-making software and risk analysis in a plurality of ways:
According to one aspect of the invention, a stand-alone and general-purpose software tool is provided for interactively modeling and solving sequential probabilistic decision and risk analysis problems on a variety of computational platforms. Intended for users ranging from decision scientists to applied decision problem solvers whose expertise in decision analysis or computer science may be limited, the tool is designed to include a graphical and algorithmic representation of modern decision theory as currently practiced by skilled decision analysts. It consists of several modules, each module representing a well-defined step in the modeling and solving of decision problems, and in conducting risk analyses and assessments.
Most decision problems are driven by a collection of competing objectives. Accordingly, a module of particular distinction enables users to express, structure and prioritize their objectives, and to seamlessly integrate the resulting structure with their decision model.
In accordance with another aspect of the invention, the method and means include an intuitive Graphical User Interface (GUI) whose internal engine is designed to guide users in the construction and execution of objectives hierarchies and decision models, and to relegate complex reasoning processes and calculations to another computational engine operating in the background. This is accomplished by providing the following salient features:
a. A multiple-window display where each window represents the current state of a corresponding module. The objectives hierarchy window, for instance, represents the module in which objectives are specified and structured. This window may be scrolled, zoomed, moved, hidden or brought forward. Similarly for the window representing the decision modeling module, and for a plurality of other windows.
b. Navigation means are provided for traveling through all the nodes of the objectives hierarchy and the decision model.
c. An expansion window is provided for editing decision models. This window displays an expanded view of the topology and semantics associated with any node selected in the decision model, and is especially useful when models contain a large quantity of nodes.
d. Yet another collection of windows is provided for recalling and executing previous projects, creating new projects, and displaying the computational results associated with previous projects. For two-way sensitivity analyses, means for rotating the three-dimensional risk surfaces about any of their three axes are provided as well.
e. A rich multi-level message structure is provided to further assist users in avoiding input errors, inconsistencies and contradictions, forbidden operations and resource constraint violations. Message levels range from purely advisory and instructional levels to critical levels designed to avoid catastrophic modeling or computational conditions.
According to yet another aspect of the invention, the method and means include interactive procedures for integrating, by the use of established rational procedures, the assessment and encoding of probabilities and utility functions with the construction of objective hierarchies and decision models.
In accordance with a final aspect of the invention, the software further includes means for solving decision problems involving multi-dimensional numerical, qualitative and linguistic performance measures defined on an absolute time scale, thereby further allowing the solution to dynamical and qualitative decision problems and risk analyses.
Objects and Advantages
Accordingly, to provide a more detailed specification of the advantages and contributions discussed in general terms in the above summary, several objects and advantages of the present invention are:
1. To provide a stand-alone software tool for interactively modeling and solving multi-dimensional sequential probabilistic decision and risk analysis problems on a variety of computational platforms without requiring significant user background in decision theory or in computer science.
2. To provide an improved Graphical User Interfaces (GUI) for decision makers and risk analysts using decision and risk analysis software.
3. To allow the seamless integration of the decision maker""s objectives, preferences and priorities during the modeling and computational phases of the decision-solving process.
4. To provide means for applying Direct Probability Computation (DPC) methods for solving probabilistic decision problems using Sequential Decision Models (SDM), said means further providing a numerical time scale on which dynamical problems can be specified.
5. To better exploit the computational advantages inherent in models with repeated sub-graphs or sub-trees.
6. To provide means for assessing and encoding probability functions, and for integrating said assessing and encoding with the construction of decision models.
7. To provide means for assessing and encoding utility functions, and for integrating said assessing and encoding with the construction of objective hierarchies and decision models.
8. To allow unconstrained policy preemptions in the construction and computation of sequential decision models.
9. To extend one-dimensional performance measures to multi-dimensional performance measures.
10. To further extend performance measures by allowing linguistic and qualitative values, thereby eliminating current restrictions to numerical values.
Still further objects and advantages will become apparent from a consideration of the ensuing description of the invention and its operation, and from the included drawings.
Background of the Second Preferred Embodiment
Since the birth of servomechanisms during the 1930s [34-42], a large body of literature has been written about the automatic control of dynamical systems and processes. During the past two decades, the size and complexity of industrial processes has increased enormously, leading to the development of hierarchical approaches with special emphasis on the control and coordination of multi-component systems [34,36,39,42,51].
Concern for the reliability, maintenance, safety, environmental and social impacts of operational systems have introduced additional complications that cannot be resolved with linear, deterministic and single-level approaches, and more powerful methods are needed. To introduce these new challenges, consider FIG. 4, where a general process control structure is represented in terms of two major levels, the process level 18 and the system level 23.
At the process level, the controlled process consists of the plant 19 and the plant regulator 20. In chemical processes, plant inputs 21 typically consist of raw products that are processed by the plant into end products shown as process outputs 22. As another example, the plant 19 may be a computer whose inputs 21 include various tasks and outputs 22 are the results of executing these tasks. Consistent with the view exhibited in FIG. 4, the plant regulator 20 embodies the control laws required to optimize parameters that are local to the process, even if the process consists of a multiplicity of widely-distributed components as would be the case when the plant is an electrical power generation and distribution network. For chemical and nuclear processes, such local parameters may include NOX, SO2 or CO emissions, maintenance and operation costs, steam waste, boiler performance, nuclear waste, local safety and reliability indices, hot water effluent and feed rates. In the control of power grids, as another example, performance parameters such as generation efficiency, line losses, reserve power, frequency of power interruptions, network interconnection and kilowatt pricing must be considered.
In contrast to the process level, the system level 23 is designed to account for issues that cannot be represented in sufficient detail using current process modeling and control methods.
These include environmental impacts and risks, equipment maintenance and replacement planning, economic and social factors, and global regulatory constraints imposed by the EPA and by the OSHA. Controls and commands at this level are thus designed to optimize higher-level and more global parameters. These commands are generated on a time scale that may be considerably larger and coarser than the scale on which local commands are executed.
As a practical example, consider a resource allocation and decision problem that arises frequently during the operation of regional electrical power generation and distribution networks. Such systems typically contain generation apparatus that produce electrical power from four basic types of fuel resources, coal, nuclear, oil, and hydroelectric. When a significant increase in demand arises at the plant input 21, and an acceptable level of service must be maintained at output 22, the system operator 24 faces several decisions in real-time. He or she must decide, for instance, whether to bring an additional generation unit of some type on line, to increase the output of one or more operating units, or to select a mixture of such policies. To simplify the example, assume that the operator""s decision is constrained to increase the power output of only one type of generating unit. He must therefore choose one of the four types, and his decision may be stated as a question: which type?
Any choice based exclusively on local process criteria will almost certainly disagree with a choice derived from the higher-level considerations discussed earlier, essentially because the consequencesxe2x80x94as measured by their utilityxe2x80x94may vary considerably. If the operator selects to increase nuclear power production, for instance, more water coolant will be needed and more hot water effluents will be produced, increasing the risks to wildlife and fisheries. Subsequent choices about the disposal and possible re-processing of spent fuel, fuel packaging, transportation and storage must be considered, leading to yet further social and environmental impacts and consequences. If the coal alternative is selected instead, air pollution will be increased and additional waste products will be produced. Coal reserves will be reduced, leading to further choices and consequences. If the oil alternative is chosen, additional choices concerning oil exploration and well drilling will be introduced. Finally, the selection of the hydroelectric choice may reduce water supplies below acceptable levels and, in periods of drought, may incur unacceptable social and political consequences.
Persons skilled in the art of process control will recognize that the higher-level issues illustrated by our simplified example involve a sequence of decisions and consequences that may reach far into a plant""s future. Considering that process command and control choices executed in the present will also produce various long-term effects that will influence these decisions and their consequences, it is imperative that current control laws be upgraded to include means for managing and controlling these effects. Referring to the first embodiment of this disclosure, this will require the use of sequential and probabilistic decision models, at least at the systems level.
Although the importance of the long-term effects exemplified above has long been recognized, the modeling and computational limitations of current control methods and software have constrained developers to provide only a rough account of these effects in their software. This important limitation in the art is due, in large part, to a fundamental incompatibility between sequential decision models and process control models. As demonstrated by the leading producers of process control software [45-49] and prominent research organizations [44], the current technology is based on the application of conventional control theory and the methods of Linear Programming, Non-linear Programming and Stochastic Programming. Probabilistic decision networks [33] and Observable Markov Processes [12, 52-54] do not fit easily into these methods, and software developers have been compelled to address the higher-level issues xe2x80x9coff-linexe2x80x9d, either as ad-hoc management exercises, or with third-party simulation and risk analysis tools.
Accordingly, several improvements to the art of process control software are needed. First, improved real-time control laws must be designed and implemented so that the resulting control settings 19 provide a full account of higher-level performance criteria and drive the process in a direction that is globally optimal. Second, and referring to our first embodiment, the objectives structure for the plant and for the overall system should also be an integral part of the system controller. Lastly, improvements in the man-machine interface 25 must be developed to assist the system operator 24 in the real-time specification, structuring and editing of the objectives hierarchy and sequential decision models integrated within the global controller.
Summary of the Second Embodiment
In the second preferred embodiment, a general object of the current invention is to upgrade current process control software by providing a method and graphically interactive means to account for sequential decisions arising at the process level and at the systems level.
According to one aspect of the second embodiment, a method is provided for modeling and solving sequential process control decisions on-line, as an integral step in the real-time formulation and execution of process control commands.
In accordance with another aspect of the invention, the method and means include an intuitive Graphical User Interface (GUI) whose internal engine is designed to guide users in the construction and execution of objectives hierarchies and decision models, and to relegate complex reasoning processes and calculations to another computational engine operating in the background. This is accomplished by providing the same salient features as were listed in the summary of the first embodiment. The remaining aspects are the same as those listed in the summary of the first embodiment.
Objects and Advantages of the Second Embodiment
Accordingly, and to provide a more detailed specification of the advantages and contributions discussed in general terms in the above summary, several objects and advantages of the second embodiment are:
a. To provide a method and graphically interactive means to account for sequential probabilistic decisions arising at the process level and at the systems level.
b. To provide a method and means for estimating, from on-line process measurements, the probabilities associated with chance nodes, and for including the probabilities in the decision model.
c. To provide a method and means for deriving, from process measurements, the values of performance measures at every node of the decision model, and for including these values in the model.
d. All the objects and advantages of the first embodiment of the current invention.